{
 "nbformat": 4,
 "nbformat_minor": 2,
 "metadata": {
  "language_info": {
   "name": "python",
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   }
  },
  "orig_nbformat": 2,
  "file_extension": ".py",
  "mimetype": "text/x-python",
  "name": "python",
  "npconvert_exporter": "python",
  "pygments_lexer": "ipython3",
  "version": 3
 },
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "最近邻规则分类KNN (K-Nearest Neighbor):\n",
    "+ 为了判断未知实例的类别，以所有已知类别的实例作为\n",
    "参照选择参数K\n",
    "+ 计算未知实例与所有已知实例的距离\n",
    "+ 选择最近K个已知实例\n",
    "+ 根据少数服从多数的投票法则(majority-voting)，让\n",
    "未知实例归类为K个最邻近样本中最多数的类别"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "算法缺点：\n",
    "+ 算法复杂度较高（需要比较所有已知实例与要分类的实例）\n",
    "+ 当其样本分布不平衡时，比如其中一类样本过大（实例数量\n",
    "过多）占主导的时候，<br>新的未知实例容易被归类为这个主导\n",
    "样本，因为这类样本实例的数量过大，但这个新的未知实例\n",
    "实际并没有接近目标样本"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 导入算法包以及数据集\n",
    "import numpy as np\n",
    "from sklearn import datasets\n",
    "from sklearn.model_selection import train_test_split\n",
    "from sklearn.metrics import classification_report,confusion_matrix\n",
    "import operator\n",
    "import random"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def knn(x_test, x_data, y_data, k):\n",
    "    # 计算样本数量\n",
    "    x_data_size = x_data.shape[0]\n",
    "    # 复制x_test\n",
    "    np.tile(x_test, (x_data_size,1))\n",
    "    # 计算x_test与每一个样本的差值\n",
    "    diffMat = np.tile(x_test, (x_data_size,1)) - x_data\n",
    "    # 计算差值的平方\n",
    "    sqDiffMat = diffMat**2\n",
    "    # 求和\n",
    "    sqDistances = sqDiffMat.sum(axis=1)\n",
    "    # 开方\n",
    "    distances = sqDistances**0.5\n",
    "    # 从小到大排序\n",
    "    sortedDistances = distances.argsort()\n",
    "    classCount = {}\n",
    "    for i in range(k):\n",
    "        # 获取标签\n",
    "        votelabel = y_data[sortedDistances[i]]\n",
    "        # 统计标签数量\n",
    "        classCount[votelabel] = classCount.get(votelabel,0) + 1\n",
    "    # 根据operator.itemgetter(1)-第1个值对classCount排序，然后再取倒序\n",
    "    sortedClassCount = sorted(classCount.items(),key=operator.itemgetter(1), reverse=True)\n",
    "    # 获取数量最多的标签\n",
    "    return sortedClassCount[0][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 载入数据\n",
    "iris = datasets.load_iris()\n",
    "# x_train,x_test,y_train,y_test = train_test_split(iris.data, iris.target, test_size=0.2) #分割数据0.2为测试数据，0.8为训练数据\n",
    "\n",
    "#打乱数据\n",
    "data_size = iris.data.shape[0]\n",
    "index = [i for i in range(data_size)] \n",
    "random.shuffle(index)  \n",
    "iris.data = iris.data[index]\n",
    "iris.target = iris.target[index]\n",
    "\n",
    "#切分数据集\n",
    "test_size = 40\n",
    "x_train = iris.data[test_size:]\n",
    "x_test =  iris.data[:test_size]\n",
    "y_train = iris.target[test_size:]\n",
    "y_test = iris.target[:test_size]\n",
    "\n",
    "predictions = []\n",
    "for i in range(x_test.shape[0]):\n",
    "    predictions.append(knn(x_test[i], x_train, y_train, 5))\n",
    "\n",
    "print(classification_report(y_test, predictions))\n",
    "\n",
    "print(confusion_matrix(y_test,predictions))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 利用sklearn 打乱数据切分数据集\n",
    "# x_train,x_test,y_train,y_test = train_test_split(iris.data, iris.target, test_size=0.2) #分割数据0.2为测试数据，0.8为训练数据\n",
    "\n",
    "#打乱数据\n",
    "data_size = iris.data.shape[0]\n",
    "index = [i for i in range(data_size)] \n",
    "random.shuffle(index)  \n",
    "iris.data = iris.data[index]\n",
    "iris.target = iris.target[index]\n",
    "\n",
    "#切分数据集\n",
    "test_size = 40\n",
    "x_train = iris.data[test_size:]\n",
    "x_test =  iris.data[:test_size]\n",
    "y_train = iris.target[test_size:]\n",
    "y_test = iris.target[:test_size]\n",
    "\n",
    "# 构建模型\n",
    "model = neighbors.KNeighborsClassifier(n_neighbors=3)\n",
    "model.fit(x_train, y_train)\n",
    "prediction = model.predict(x_test)\n",
    "\n",
    "print(classification_report(y_test, prediction))"
   ]
  }
 ]
}